Cryptography Engineering by Niels Ferguson & Bruce Schneier & Tadayoshi Kohno

Author:Niels Ferguson & Bruce Schneier & Tadayoshi Kohno
Language: eng
Format: epub
Publisher: Wiley
Published: 2011-01-27T05:00:00+00:00

10.2 Generating Small Primes

Sometimes it is useful to have a list of small primes, so here is the Sieve of Eratosthenes, which is still the best algorithm for generating small primes. The 220 in the pseudocode below is a stand-in for any appropriate small constant.

function SMALLPRIMELIST

input: n Limit on primes to generate. Must satisfy 2 ≤ n ≤ 220.

output: P List of all primes ≤n.

Limit the size of n. If n is too large we run out of memory.

assert 2 ≤ n ≤ 220

Initialize a list of flags all set to one.

(b2, b3, …, bn) ← (1, 1, …, 1)

i ← 2

while i2 ≤ n do

We have found a prime i. Mark all multiples of i composite.

for j ∈ 2i, 3i, 4i, …, n/i i do

bj ← 0

od

Look for the next prime in our list. It can be shown that this loop never results

in the condition i > n, which would access a nonexistent bi.

repeat

i ← i + 1 bi=1

od

All our primes are now marked with a one. Collect them in a list.

P ← []

for k ∈ 2, 3, 4, …, n do

if bk = 1 then

P ← P || k

fi

od

return P

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.